Otimização Convexa: Os Fundamentos da Aproximação por Norma

Imaginemos que você é um alfaiate tentando ajustar um terno padrão (o espaço gerado por $A$) a um cliente com proporções únicas (o vetor $b$). Não importa quão bem você ajuste as mangas ou a cintura (os coeficientes $x$), o terno nunca será um ajuste perfeito. Você está procurando o "melhor" compromisso — uma aproximação por norma que minimiza a tensão ou o "resíduo" em cada costura.

O Quadro Matemático

O objetivo central é encontrar um vetor $x \in \mathbb{R}^n$ tal que a combinação linear $Ax = x_1a_1 + \dots + x_na_n$ melhor aproxime $b$. Isso é frequentemente referido como a regressão de $b$ sobre os regressores (as colunas de $A$).

Focamos no vetor de resíduos $r = Ax - b$. Na prática, assumimos um sistema sobredeterminado onde $m > n$. Por quê? Porque quando $m = n$ e $A$ é não singular, o ponto ótimo é simplesmente $A^{-1}b$, resultando em erro zero — um caso trivial para otimização.

🎯 Princípio Fundamental

O problema de aproximação por norma (6.1) é um problema convexo e é garantido ser solucionável. Sempre existe pelo menos uma solução ótima $\hat{x}$ que minimiza a distância entre o alvo e o subespaço alcançável.

Variações Canônicas

Dependendo do "tipo" de erro que queremos penalizar, escolhemos diferentes normas:

1. Mínimos Quadrados ($\ell_2$)

A abordagem mais comum. Minimiza a soma dos quadrados dos resíduos: $\|Ax - b\|_2^2$. É sensível a grandes valores discrepantes, mas oferece uma solução analítica através das equações normais.

2. Chebyshev / Minimax ($\ell_\infty$)

Minimiza o máximo absoluto $\max_i |r_i|$. É usado quando cada medição individual deve permanecer dentro de uma tolerância estrita. Pode ser resolvido por meio do seguinte Programa Linear (PL):

minimize $t$
sujeito a $-t\mathbf{1} \preceq Ax - b \preceq t\mathbf{1}$

3. Soma dos Valores Absolutos dos Resíduos ($\ell_1$)

Minimiza $\sum |r_i|$. Essa abordagem é robusta a valores discrepantes, pois não eleva ao quadrado os erros. Também pode ser resolvida por meio de um PL:

minimize $\mathbf{1}^T t$
sujeito a $-t \preceq Ax - b \preceq t$

Contexto de Estimação

Em muitas áreas da engenharia, assumimos que um estado verdadeiro $x$ é obscurecido por ruído: $y = Ax + v$. Nosso objetivo é encontrar uma estimativa $\hat{x} = \text{argmin}_z \|Az - y\|$. Ao escolher a norma, estamos efetivamente fazendo uma suposição sobre a distribuição estatística do ruído $v$.

\text{Minimize } \|u - b\| \text{ sujeito a } u \in \mathcal{A} \quad (\text{onde } \mathcal{A} = \text{Range}(A))

PERGUNTA 1

No contexto da aproximação por norma, por que geralmente assumimos que $m > n$?

Porque se $m = n$, a solução é trivial $x = A^{-1}b$ com resíduo zero.

Para garantir que o problema permaneça não convexo.

Porque a norma L1 exige mais variáveis do que restrições para ser solucionável.

Para garantir que a matriz A seja sempre singular.

PERGUNTA 2

Qual formulação de Programação Linear (PL) representa corretamente o problema de aproximação de Chebyshev (minimax)?

minimize t sujeito a -t1 ⪯ Ax - b ⪯ t1

minimize 1ᵀt sujeito a -t ⪯ Ax - b ⪯ t

minimize ||Ax - b||₂ sujeito a x ⪰ 0

minimize t sujeito a Ax - b = t

PERGUNTA 3

Você está calibrando um sensor e deseja garantir que nenhuma medição individual jamais se desvie do modelo por mais do que uma quantidade fixa. Qual norma você deveria usar?

L∞ (Chebyshev)

L₁ (Soma dos Valores Absolutos dos Resíduos)

L₂ (Mínimos Quadrados)

A Norma de Frobenius

PERGUNTA 4

O que é verdade sobre a solubilidade do problema de aproximação por norma (6.1)?

É sempre solucionável e convexo.

É solucionável apenas se a matriz $A$ for simétrica.

É não convexo se a norma L1 for usada.

Não tem solução se o sistema for sobredeterminado.

PERGUNTA 5

Na expressão $y = Ax + v$, se $v$ representa ruído de Laplace (que possui caudas mais pesadas do que o ruído gaussiano), qual norma de aproximação é estatisticamente mais robusta?

L₁ (Soma dos Valores Absolutos dos Resíduos)

L₂ (Mínimos Quadrados)

L∞ (Chebyshev)

pseudo-norma L₀